package com.yulongtian.weekCompetition.month202302.week02;


import java.util.Arrays;

/**
 * 自己想到了二分，但是边界没有搞明白
 * 参考他人二分 可
 *
 * @author yulongTian
 * @create 2023-02-12 10:37
 */
public class Test02 {
    public static void main(String[] args) {
        int[] nums = {1, 7, 9, 2, 5};
//        int[] copy = Arrays.copyOfRange(nums, 1, 3);
//        System.out.println(Arrays.toString(copy));
        int lower = 11;
        int upper = 11;
        System.out.println(countFairPairs(nums, lower, upper));
    }

    /**
     * 两个数：
     * 枚举一个数，去看另外一个数可以是哪些值
     * <p>
     * nums[i]的范围[lower-nums[j],upper-nums[j]]
     * <p>
     * <= upper - nums[j]的数的个数          即>upper - nums[j]第一个数的下标</=>
     * 减去 < lower - num[j]的数的个数       即>=lower - num[j]第一个数的下标</>
     *
     * @param nums
     * @param lower
     * @param upper
     * @return
     */
    public static long countFairPairs(int[] nums, int lower, int upper) {
        long ans = 0L;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //左闭右开
            int l = binaryLeft(nums, 0, i, lower - nums[i]);
            int r = binaryRight(nums, 0, i, upper - nums[i]);
            ans += r - l;
        }
        return ans;
    }

    //找到第一个 ≥ lower 的元素
    public static int binaryLeft(int[] nums, int l, int r, int lower) {
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= lower) r = mid;
            else l = mid + 1;
        }
        return l;
    }

    //找到第一个 > upper的元素
    public static int binaryRight(int[] nums, int l, int r, int upper) {
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] > upper) r = mid;
            else l = mid + 1;
        }
        return l;
    }

//    //暴力2个for循环超时
//    //47 / 51 个通过测试用例
//    public static long countFairPairs(int[] nums, int lower, int upper) {
//        long ans = 0L;
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                if (lower <= nums[i] + nums[j] && upper >= nums[i] + nums[j]) {
//                    ans++;
//                }
//            }
//        }
//        return ans;
//    }

//    public static long countFairPairs(int[] nums, int lower, int upper) {
//        long ans = 0L;
//        int n = nums.length;
//        for (int i = 0; i < nums.length; i++) {
//            int[] copy = Arrays.copyOfRange(nums, i + 1, n);
//            int left_tar = lower - nums[i];
//            int right_tar = upper - nums[i];
//            Arrays.sort(copy);
//
//            int l = 0;
//            int r = 1;
//
//            for (int j = 0; j < copy.length; j++) {
//                if (copy[j] >= left_tar) {
//                    l = j;
//                    break;
//                }
//                if (j == copy.length - 1) {
//                    l = copy.length;
//                }
//            }
//            for (int j = copy.length - 1; j >= 0; j--) {
//                if (copy[j] <= right_tar) {
//                    r = j;
//                    break;
//                }
//                if (j == 0) {
//                    r = -1;
//                }
//            }
//            if (r < l) {
//                continue;
//            }
//            ans += r - l + 1;
//        }
//        return ans;
//    }
//
//
//    //二分  还有问题
//    public static int binarySearch(int[] copy, int target) {
//        int left = 0;
//        int right = copy.length - 1;
//        while (left < right) {
//            int mid = left + (right - left) / 2;
//            if (copy[mid] > target) {
//                right = mid - 1;
//            } else if (copy[mid] < target) {
//                left = mid + 1;
//            } else {
//                return mid;
//            }
//        }
//        return left + (right - left) / 2;
//    }

}
